package com.cjm.algorithm.leetcode.listnode;

import com.cjm.algorithm.ListNode;
import com.cjm.algorithm.ListNodeHelp;

public class Ti92Medium {
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 定义一个dummyHead, 方便处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // 将指针移到相应的位置
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // 头插法插入节点
        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        return dummyHead.next;
    }

    public static ListNode reverseBetween1(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(0);// 新建出这么一个虚拟的头节点
        dummyHead.next = head;// 它的下一个节点就是头节点
        ListNode g = dummyHead;// 门卫
        ListNode p = dummyHead.next;// 将要转到最后一们的节点
        for (int i = 0; i < left - 1;i++) {
            g = g.next;p = p.next;// 一直移动到目标的位置
        }
        // 这里就是说, 要移动多少个节点
        for (int i = 0; i < right - left; i++) {
            ListNode temp = p.next;// 将要移动的节点, 把它给提出来
            p.next = temp.next;

            temp.next = g.next;
            g.next = temp;
        }
        return dummyHead.next;
    }

    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        // 这个是抄的, 头插法
        // 有一个虚拟的节点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode g = dummyNode;
        ListNode p = dummyNode.next;
        // 这里为什么是left - 1呢?之所以觉得这里不对劲, 是因为题目上是从1开始的, 但是呢, 这里又是从0开始的, 不适应
        // 所以我们还是从1开始吧
        for (int i = 1;i<left;i++) {
            g = g.next;p=p.next;
        }

        for (int i = 0; i < right - left; i++) {
            ListNode temp = p.next;
            p.next = temp.next;

            temp.next = g.next;
            g.next = temp;
        }
        return dummyNode.next;
    }


    public static void main(String[] args) {
        ListNode listNode = ListNodeHelp.toListNode(new int[]{1, 2, 3, 4, 5});
        ListNodeHelp.printListNode(listNode);
        reverseBetween(listNode, 2, 4);
        System.err.println("OK");
    }
}
